//割边判断条件:low[v]>dfs[u]
//割点判断条件:1. 如果不是根节点,low[v]>=dfs[u],u是割点;2. 如果是根节点,子节点两个及以上就是割点,也就是进visit[v]==0判断两次
//强联通分量判断条件: 几乎一致，但是需要用栈来处理，https://blog.csdn.net/farines/article/details/98999788
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1192 {

    int time=0;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        int[] first=new int[n];
        Arrays.fill(first,-1);
        int[] next=new int[connections.size()*2];
        int[] go=new int[connections.size()*2];
        int count=0;
        for (List<Integer> connection : connections) {
            int x=connection.get(0),y=connection.get(1);
            next[count]=first[x];
            first[x]=count;
            go[count]=y;
            count++;
            next[count]=first[y];
            first[y]=count;
            go[count]=x;
            count++;
        }
        int[] dfs=new int[n];
        int[] low=new int[n];
        int[] visit=new int[n];
        visit[0]=1;
        List<List<Integer>> ans=new ArrayList<>();
        tarjan(0,-1,first,next,go,dfs,low,visit,ans);
        return ans;
    }

    private void tarjan(int k, int last, int[] first, int[] next, int[] go, int[] dfs, int[] low, int[] visit, List<List<Integer>> ans) {
        dfs[k]=low[k]=++time;
        int p=first[k];
        while (p!=-1){
            int v=go[p];
            if (visit[v]==0){
                visit[v]=1;
                tarjan(v,k,first,next,go,dfs,low,visit,ans);
                low[k]=Math.min(low[k],low[v]);
                if (low[v]>dfs[k]){
                    ans.add(Arrays.asList(k,v));
                }
            }else if (v!=last){
                low[k]=Math.min(low[k],dfs[v]);
            }

            p=next[p];
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1192().criticalConnections(4,Arrays.asList(Arrays.asList(0,1),Arrays.asList(1,2),Arrays.asList(2,0),Arrays.asList(1,3))));
    }
}
